5

Hard examples for the bounded depth Frege proof system

Year:
2002
Language:
english
File:
PDF, 297 KB
english, 2002
6

Random Cnf’s are Hard for the Polynomial Calculus

Year:
2010
Language:
english
File:
PDF, 457 KB
english, 2010
13

Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs

Year:
2007
Language:
english
File:
PDF, 261 KB
english, 2007
14

An Additive Combinatorics Approach Relating Rank to Communication Complexity

Year:
2014
Language:
english
File:
PDF, 181 KB
english, 2014
19

Robust locally testable codes and products of codes

Year:
2006
Language:
english
File:
PDF, 178 KB
english, 2006
20

Space Complexity in Propositional Calculus

Year:
2002
Language:
english
File:
PDF, 311 KB
english, 2002
22

Short proofs are narrow---resolution made simple

Year:
2001
Language:
english
File:
PDF, 167 KB
english, 2001
23

Affine Dispersers from Subspace Polynomials

Year:
2012
Language:
english
File:
PDF, 429 KB
english, 2012
25

Near Optimal Separation Of Tree-Like And General Resolution

Year:
2004
Language:
english
File:
PDF, 278 KB
english, 2004
28

From Affine to Two-Source Extractors via Approximate Duality

Year:
2015
Language:
english
File:
PDF, 348 KB
english, 2015
30

Composition of semi-LTCs by two-wise tensor products

Year:
2015
Language:
english
File:
PDF, 504 KB
english, 2015
34

A combinatorial characterization of smooth LTCs and applications

Year:
2016
Language:
english
File:
PDF, 237 KB
english, 2016
36

Size-Space Tradeoffs for Resolution

Year:
2009
Language:
english
File:
PDF, 230 KB
english, 2009
37

Some 3CNF Properties Are Hard to Test

Year:
2005
Language:
english
File:
PDF, 248 KB
english, 2005
41

Subspace Polynomials and Cyclic Subspace Codes

Year:
2016
Language:
english
File:
PDF, 229 KB
english, 2016
42

Space complexity of random formulae in resolution

Year:
2003
Language:
english
File:
PDF, 158 KB
english, 2003
44

Sound 3-Query PCPPs Are Long

Year:
2009
Language:
english
File:
PDF, 400 KB
english, 2009
49

Towards lower bounds on locally testable codes via density arguments

Year:
2012
Language:
english
File:
PDF, 498 KB
english, 2012
50

Sparse affine-invariant linear codes are locally testable

Year:
2017
Language:
english
File:
PDF, 578 KB
english, 2017